//
// Created by liushuai on 2021/1/26.
//

#include "reverseKGroup.h"

int linkLength(ListNode *head) {
    int count = 0;
    while (head) {
        head = head->next;
        count += 1;
    }
    return count;
}

ListNode *reverseKGroup(ListNode *head, int k) {
    int length = linkLength(head);
    if (length < k)
        return head;
    int seg = length / k;
    ListNode *currentNode = head;
    ListNode *nextNode;
    ListNode *segTail = nullptr;
    ListNode *newHead = nullptr;

    for (int i = 0; i < seg; i++) {
        ListNode *preNode = nullptr;
        for (int j = 0; j < k; j++) {
            nextNode = currentNode->next;
            currentNode->next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }//每一段转换为a->b->null
        if (!segTail) {
            newHead = preNode;//设置新链表头
            ListNode* temp = preNode;
            while (temp&&temp->next){
                temp = temp->next;//找到段的最后一个元素作为段连接下一段的元素
            }
            segTail = temp;

        } else {
            segTail->next = preNode;
            ListNode *temp = preNode;
            while (temp&&temp->next) {
                temp = temp->next;
            }
            temp->next = segTail;
            segTail = temp;
        }
    }
    segTail->next = currentNode;
    return newHead;
}